Field of the Invention
This invention relates to dynamic memory systems generally and in particular to dynamic memories employing non-cyclic memory transformations and processes for rapid random and sequential accessing of data in such memories.
Dynamic memories are memories in which the data stored in the memory cells are constantly being rearranged in accordance with operations called memory transformations, which are applied to the memory. An example of one of the simplest types of such memories is a shift register employing a cyclic end-around shift. Individual data are stored in each shift register stage, with one of such stages being used as a read/write port for the input and the output of data. Each datum is shifted from one stage to the next, end-around. In order to access a given datum to the read/write port of a shift register memory of size N, on the average, (N-1)/2 cyclic shifts are necessary. For reasonable size memories, N is usually quite large and consequently, long access times are involved. This is a significant disadvantage with cyclically interconnected shift register memories.
Once a given datum has been randomly accessed, it is commonly required to sequentially access successive data stored in adjacent memory cells. The cyclic shift register has the advantage that sequential accessing of data can be performed in unit time, i.e., each additional datum can be accessed with one shift. Unfortunately, this advantage is usually more than off-set by the lengthy random access time required for the first datum.
In order to reduce the access time of dynamic memories, various complex interconnection schemes have been proposed for performing non-cyclic memory transformations for rearranging the data. One such transformation is the so-called "perfect shuffle" in which the data is rearranged in a manner similar to one in which the cards of a deck are rearranged when shuffled. To illustrate, if a deck of cards is divided in half and the cards from the two halves are perfectly interlaced with the previously top card remaining on top, the resulting arrangement of the deck is equivalent to the rearrangement of data in a dynamic memory as a result of the perfect shuffle operation. Such a memory transformation may be easily implemented in a shift register dynamic memory by simply interconnecting the appropriate inputs and outputs of the shift register stages. Upon the application of a shift control signal to the shift register, the contents of the register stages are simultaneously rearranged in accordance with the interconnections among stages. In order to employ this and similar non-cyclic types of memory transformations, accessing algorithms must obviously be found which will keep track of the memory state and permit the desired data to be accessed.
Another transformation which has been proposed is the "exchange shuffle" in which the contents of adjacent even-odd stages are first pairwise interchanged, then the data is rearranged in accordance with the perfect shuffle. A memory employing both the perfect shuffle and exchange shuffle interconnections has been described in "Dynamic Memories With Enhanced Data Access," I.E.E.E. Trans. Comput., vol C-21, No. 4, pp 359-366, 1972, by H. S. Stone. Stone demonstrates that a memory of size N=2.sup.m stages employing these transformations can randomly access data in the theoretical minimum time, shown to be log.sub.2 N=m units of time. The disadvantages of this memory as described in the paper, are that (1) once a datum has been accessed, each successive datum must be accessed using the random accessing algorithm, there being no convenient algorithm for sequentially accessing successive data in unit time; and (2) Stone's random accessing algorithm is limited to the first cell, cell 0, which is designated as the read/write port of the memory.
Aho and Ullman, U.S. Pat. No. 3,810,112, disclose a shift-shuffle memory system which employs the perfect shuffle and cyclic shift interconnections. This memory has the property that after the first two data of a sequence have been randomly accessed, successive data can be sequentially accessed in unit time, i.e., with each shift of the memory. The disadvantages of this memory are that the random access time for each datum is approximately twice that required by Stone's memory, i.e., twice the theoretical minimum time, but more importantly, Aho and Ullman's memory is limited to memories of size 2.sup.r -1, i.e., odd-sized memories of size one less than a power of 2. Aho and Ullman's memory also requires that data be accessed through the first stage, stage 0, since the accessing algorithm which they utilize, is limited to this stage alone.
Although not directed to a memory system per se, U.S. Pat. No. 3,605,024 to Batcher, discloses a system similar to that of Aho and Ullman, in which a shift register of length m=2.sup.p -1 stages employs shuffle type interconnections among the stages, such that any cyclic end-around shift may be accomplished in p shift times. For example, a 15 stage register, m=15=2.sup.4 -1, can be shifted any number of places between 0-15 in 4 shift times, using two sets of interconnections between stages. Batcher's system is limited only to registers of certain lengths. All even numbered lengths, including lengths equal to a power of 2 are excluded. Random or sequential accessing of data is not provided.
H. S. Stone in "Dynamic Memories with Fast Random and Sequential Access," I.E.E.E. Trans. Comput., vol C-24, pp 1168-1174, 1975, proposes minor variations and improvements in Aho and Ullman's memory access algorithm which simplifies its implementation and improves the random access time slightly. Stone further discusses his previously proposed perfect shuffle/exchange shuffle memory of a size equal to a power of 2, which has good random access properties but not necessarily the sequential access property. Although Stone recognizes certain advantages to the Aho and Ullman memory, he states at page 1174:
". . . Such memories have an annoying property that they do not contain a number of words equal to a power of 2. Thus if such memories are modularized, it is awkward to construct memories composed of two or more individual memory modules. It is best to have modules containing a number of words exactly equal to a power of 2 in this case, so that modules are selected by specific bits in a binary address."
The problem to which Stone refers is significant where such memories are used in data processing equipment. The architecture of most computers is such that memory modules having a size equal to a power of 2 are required. Otherwise, it becomes difficult to build up memories using individual modules connected together and requires that complex memory addressing schemes be devised.
With respect to sequential accessing in non-cyclically connected memories such as the perfect shuffle/exchange shuffle memory, Stone demonstrates that sequential accessing depends upon the existence of sequences of operations, called tours, which cause each datum in the memory to visit the read/write port exactly once for each complete memory cycle. Stone states that there exist three such distinct tours at the first storage locations for memories of size 2.sup.3 =8, fourteen for memories of size 2.sup.4 =16 and none for memories of size 2.sup.5 =32. The question of the existence of tours for memories of size 2.sup.6 =64 and greater was left unanswered.
Thus, in summary, no prior art memory has been able to combine in one memory, convenient size, minimum theoretical random access time and good sequential accessing properties. Memories such as Stone's shuffle/exchange memory, while possessing good access time and size equal to powers of 2 do not always have good sequential accessing properties. Conversely, in memories such as the Aho and Ullman memory which employs cyclic connections, sequential accessing is always possible. However, such memories do not have good access time and are limited to a size equal to one less than a power of 2, i.e., N=2.sup.r -1.
The present invention overcomes these disadvantages by combining in a single memory the flexibility of a memory size equal to any odd number or any power of 2, minumum theoretical random access time and good sequential accessing properties. Furthermore, the accessing algorithms presented permit data to be accessed through any port of the memory, not just the first stage as required by prior art memories.